package formal.tree.recursion;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 合并二叉树
 *
 * @author DengYuan2
 * @create 2021-01-12 19:50
 */
public class E_617 {
    public static void main(String[] args) {
        Integer[] a = {1, 3, 2, 5, null, null, null};
        Integer[] b = {2, 1, 3, null, 4, null, 7};
        TreeNode t1 = TreeNode.generateTree(a);
        TreeNode t2 = TreeNode.generateTree(b);
        TreeNode treeNode = mergeTrees3(t1, t2);
        treeNode.pre(treeNode);
    }

    /**
     * 我的写法
     *
     * @param t1
     * @param t2
     * @return
     */
    public static TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) {
            return null;
        } else if (t1 != null && t2 != null) {
            t1.val += t2.val;
        } else if (t1 == null && t2 != null) {
            return t2;
        } else {
            return t1;
        }
        t1.left = mergeTrees(t1.left, t2.left);
        t1.right = mergeTrees(t1.right, t2.right);
        return t1;
    }

    /**
     * 官方-递归
     * 前面几步更加简单
     * 我是在t1上修改，他是新建立节点，保证原有的树都不被改变
     *
     * @param t1
     * @param t2
     * @return
     */
    public static TreeNode mergeTrees2(TreeNode t1, TreeNode t2) {
        if (t1 == null) {
            return t2;
        }
        if (t2 == null) {
            return t1;
        }
        TreeNode root = new TreeNode(t1.val + t2.val);
        root.left = mergeTrees2(t1.left, t2.left);
        root.right = mergeTrees2(t1.right, t2.right);
        return root;
    }

    /**
     * 官方-广度优先遍历
     *
     * @param t1
     * @param t2
     * @return
     */
    public static TreeNode mergeTrees3(TreeNode t1, TreeNode t2) {
        if (t1 == null) {
            return t2;
        }
        if (t2 == null) {
            return t1;
        }
        Queue<TreeNode> q1 = new LinkedList<>();
        q1.offer(t1);
        Queue<TreeNode> q2 = new LinkedList<>();
        q2.offer(t2);
        LinkedList<TreeNode> resQueue = new LinkedList<>();
        resQueue.offer(new TreeNode(t1.val + t2.val));
        TreeNode root = resQueue.peek();
        while (!q1.isEmpty() && !q2.isEmpty()) {
            TreeNode f = resQueue.poll();
            TreeNode f1 = q1.poll();
            TreeNode f2 = q2.poll();
            if (f1.left != null && f2.left != null) {
                q1.offer(f1.left);
                q2.offer(f2.left);
                TreeNode treeNode = new TreeNode(f1.left.val + f2.left.val);
                f.left = treeNode;
                resQueue.offer(treeNode);
            } else {
                f.left = (f1.left == null ? f2.left : f1.left);
            }
            if (f1.right != null && f2.right != null) {
                q1.offer(f1.right);
                q2.offer(f2.right);
                TreeNode treeNode = new TreeNode(f1.right.val + f2.right.val);
                f.right = treeNode;
                resQueue.offer(treeNode);
            } else {
                f.right = (f1.right == null ? f2.right : f1.right);
            }
        }

        return root;
    }
}
